package 优先算法.递归_搜索与回溯.初学递归.反转链表;


/**
 *https://leetcode.cn/problems/reverse-linked-list/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        Solution.ListNode list = new Solution.ListNode(1);
        list.next = new Solution.ListNode(2);
        list.next.next = new Solution.ListNode(3);
        list.next.next.next = new Solution.ListNode(4);
        Solution.ListNode listNode = so.reverseList(list);
        Solution.ListNode cur = listNode;
        while(cur != null){
            System.out.print(cur.val + "");
            cur = cur.next;
        }
    }
}

class Solution {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode Last = null;
        ListNode cur = head;
        while(cur != null){
            Last = cur;
            cur = cur.next;
        }
        dfs(head);
        return Last;
    }
    public static void dfs(ListNode head) {
        if(head == null)return;
        ListNode cur = head;
        if(cur.next == null) {
            return;
        }
        dfs(cur.next);
        cur.next.next = cur;
        cur.next = null;
    }
}